Design methodologies for essentially digital systems often deal with a particular abstraction level (RASSP Taxonomy Working Group, RASSP VHDL Modeling Terminology and Taxonomy, revision 2.3, Jun. 23, 1998 http://www.atl.external.lmco.com/rassp/taxon/rassp_taxon.html). The abstraction level of a system model is an indication of the degree of implementation detail contained within the model. Abstraction levels with increasing amount of detail form a hierarchy of abstraction levels. A design at a given abstraction level is described in terms of a set of constituent terms and their interrelationships or protocols, which in turn can be decomposed into their constituent parts at a lower level of abstraction, i.e. a higher level of refinement. Level of abstraction may be seen as the inverse or compliment of resolution, detail or granularity.
When dealing with essentially digital systems an abstraction may be described by its functional form. For instance, a system level model is a description in which a complex system is described as a composition of subsystems. Each of the subsystems may be described as a sequential process, whereby the processes may run concurrently and may use various communication mechanisms or protocols for interaction with other subsystems or systems.
An algorithmic level model describes how the system consumes input values supplied to its inputs in order to deliver the required answers to its outputs. Operations are grouped into algorithms.
A register-transfer level model describes a system in terms of registers, i.e. elemental storage for data, combinational circuitry, low-level buses and control circuits, usually implemented as finite state machines. A hardware model at the logic level describes a system in terms of equivalent Boolean logic functions and simple memory devices as flip-flops. A hardware model at the circuit level describes a system in terms of electronic components such as transistors, resistors, capacitors.
Besides abstraction levels for the description of a system there are also three further system aspects which are important. A first aspect of a system is its functionality. Another aspect of a system is its structure. This aspect describes how the system is mapped to a structure. With structure is meant an indication of how a system may be split into parts including describing a hierarchy between the parts and an indication of how these parts are interconnected. A third aspect of a system is its timing.
Also various ways of representing a system, also denoted computation models, are known. These computation models are often associated with a particular abstraction level although this is not necessary. In addition various modelling styles are known. A modelling style often comprises a computation model plus an interpretation of the computation model in terms of the implementation aspects and some application-domain specific support.
Two known computation models are situated at the algorithmic level. A data flow graph describes an algorithm in terms of its inherent data dependencies of its mathematical operations. A token based performance model, typically used for representing a multiprocessor, does not model data values except control information. This type of model is used to resolve timing aspects of a system.
A particular way of representing a system is to describe it as a set of interacting or communicating processes, also denoted tasks or threads. Each process thread comprises a set of operations, any operation possibly performing operations on a data structure which may be dedicated for that process or may be shared by a plurality of processes. Interaction or communication between processes may take place via accesses to data structures, shared by the processes. This way of representing a system as a multitude of threads is called a multi-threading approach.
An executable system model is a description of a system that can be executed or simulated on a processing engine, e.g. a computing system, at any time during the design of the system under consideration. When a system, represented as a multitude of threads, is to be executed or simulated, a thread selection scheme or scheduler determines the order in which threads are executed by interleaving and parallel execution of threads.
Multi-threading should not be confused with multi-tasking and multi-processing. With multi-tasking it is meant that the computer system (and its operating system) on which simulations takes place supports the simultaneous execution of multiple tasks. This can be through scheduling tasks by distributing the tasks over several processors. A multi-tasking supporting computer can be exploited for implementing a multi-threading approach. In principle, multi-threading does not need multi-tasking nor is multi-tasking limited to multi-threading applications. Multi-tasking can lead to reduced simulation times. Although other interpretations of multi-tasking and multi-threading are known, it can be said that within the context of the present invention, multi-tasking is related to implementation of the simulation while multi-threading is related to the conceptual representation of a system in a simulation model.
As a simplified summary, multi-threading refers to user-level parallelism, multi-tasking refers to operating-system-level parallelism and multi-processing refers to hardware-level parallelism. Multi-threading and multi-tasking are strongly related and are often used interchangeably; both providing a representation of parallelism to the user and may or may not take advantage of parallel hardware or multi-processing. Real parallel execution and a real speedup of the simulation requires hardware-level parallelism or multi-processing.
As designs are becoming more complex and because there is an on-going requirement for the design times to be reduced, digital system design conventionally starts by representing said digital system at high abstraction levels.
In a strict top-down sequential design flow an electronic system is first designed at a high, purely functional abstraction level. Only when the high-level functional design is completed is the design is continued at a lower abstraction level by adding structure and timing detail. One conventional approach is to traverse from the system-level to the algorithmic level, the register-transfer level, the logic level and finally the circuit-level.
Such a top-down design strategy does however not fully comply with a natural way of designing nor is it always possible to use such a strategy. During design designers would prefer to start refining part of the design to lower abstraction levels while leaving other parts of the design at higher levels of abstraction. Moreover designers typically prefer to introduce the different aspects of parts of their design simultaneously. As such designers would prefer a concurrent refinement procedure. Two types of concurrent refinement have been identified above. A first type is concurrent refinement of parts of the design. A second type is concurrent refinement of different aspects of parts of the design.
As one of the aspects of a design is its timing, it would be preferable to allow introduction of timing at high abstraction levels. High-level descriptions are often given in a natural language. Fast reliable design strategies require, however, executable models of the digital system under consideration so that the execution of the design can be checked at any stage. Ideally, simulation or execution of the models should be efficient, thus resulting in short simulation times in order to reduce the design time.
The timing aspect of a design can be incorporated when a multi-threading concept is used for representing a system. However, the timing concept used in conventional methodologies is not based on advanced thread selection schemes but for instance on a sequential processing of the threads, resulting in low simulation efficiency.
To summarise it can be concluded that there is a need for a design methodology and environment for essentially digital systems, enabling design initially at high-abstraction levels and supporting concurrent refinement of parts of said design as well as enabling introduction of different aspects of said design simultaneously. Different computation models and modelling styles should preferably be exploitable in the methodology. The design methodology and environment should enable incorporating timing, which is one of the aspects of a design, at all possible abstraction levels. The models used in such a methodology should preferably be executable, thus enabling simulation at any time during the design process. This allows extraction of characteristics of the design at any time during the design process. The design methodology and environment should preferably result in high simulation efficiency. providing a design methodology and design environment satisfying all the above stated requirements has proved to be difficult.
Available languages such as OMT, SDL, C++ (A. Olsen et al, Systems Engineering Using SDL-92, ISBN 0-444-89872-7, Elsevier Science B. V.,1994, Bell Education Centre, SDL, Notes of SDL introductory course, 1997) do not support concurrent refinement of different aspects of the design in the design process adequately as it is difficult to incorporate aspects of structure and timing in models defined at a high abstraction level. C++ does not support timing. OMT models are not executable. Traditional system design methodologies, such as VHDL, which include timing are oriented only on the register-transfer level which is a low level abstraction. Behavioural VHDL incorporates timing but only supports a limited computation model, in particular signals and has a very low simulation efficiency. Known high-level object-oriented design methodologies do not include timing at all abstraction levels. Although in the environment and methodology described in EP 772 140 aspects of a digital system such as functionality, structure or architecture and timing, denoted there as communication or concurrency are defined, it is assumed in this known methodology that the functionality of the digital design is fully available. A methodology with refinement means mapping functionality to an architecture, taking into account communication and concurrency. Concurrent refinement of the three aspects of a digital system namely, functionality, timing and structure, is not supported in such an environment. In this known environment timing is done via communication and concurrency but is not supported at all abstraction levels.
Known multi-threading system models, even without real data-sharing, like SDL (Specification Description Language) are non-deterministic (resulting in long analysis time). The deterministic models, like Kahn process networks (G. Kahn, The Semantics of a Simple Language for Parallel Programming, Proc. of the IFIP Congress 74, North-Holland Publishing Co., 1974) which is a specific form of data flow process networks, only allow a very restricted interprocess communication and have no time concept.
In the article by D. B. Lidsky and J. M. Rabaey, “The conceptual-level design approach to complex systems”, Journal of VLSI signal processing 18,11-24, 1998, Kluwer Academic Publishers, the Netherlands a design methodology is described which does not result in an executable model. In the presentation by J. S. Young, J. MacDonald, M. Shilman, A. Tabbara, P. Hilfinger and A. R. Newton, presented at DAC98, June 1998 timing is introduced at all abstraction levels but only for one particular (and thus only for a restricted) computation model. In the article by M. C. Little and D. L. McCue, “Construction and Use of a Simulation Package in C++”, http://cxxsim.ncl.ac.uk/homepage.html a multi-threading simulation language is disclosed. The timing aspects, supported by the language are, however, not adapted to digital system design.
Simulation efficiency can be obtained by using multi-tasking when possible, for instance when a multi-processor computing environment can be exploited. Simulation efficiency can also be obtained by preventing context switching. Indeed when the scheduler decides to execute another thread the local data of thread has to be loaded, which takes some simulation time. This is called context switching. Efficient simulation requires a method whereby the context is only switched when necessary, for instance, due to interprocess communication. Context switching can be avoided by concurrent execution of threads, which is a third type of concurrency. Existing approaches for simulation efficiency optimisation are based on initially neglecting interprocess communication and then rolling back the simulation when it is discovered that interprocess communication has taken place. Such an approach is however limited to simulations with a very restricted time concept. Such an approach requires that all interprocess communication and the internal state of each process are made accessible to the scheduler, which is not always possible or desirable.
Simulation of design models should preferably be deterministic. The thread selection schemes should preferably result in a deterministic behaviour of the system, e.g., when the same stimuli or inputs are applied to the modelled system, the simulation should be performed in the same order (same selection of the threads) and thus result in the same output. Deterministic behaviour results in less analysis time when compared to non-deterministic systems.
In particular, the design models should include at least timing information to reduce non-determinism and the simulation of the design models should be reproducible: when the scheduler has a choice because the model is non-deterministic, it should always make the same choice.